package main

import ("fmt")
// func colorTheGrid(m int, n int) int {
// 	mod := int(1e9 + 7)
//     dp := make([][]int, 3)
//     for i := 0; i < 3; i++ {
//         dp[i] = make([]int, m * n) 
//     }
//     dp[0][0] = 1
//     dp[1][0] = 1
//     dp[2][0] = 1
	
// 		for j := 1; j < m * n; j++ {
// 			r := j / m
// 			c := j % m
// 			u, l := 1, 1
// 			for i := 0; i < 3; i++ {
// 				if r > 0  {
// 					u = (dp[(i + 1) % 3][j - m] + dp[(i + 2) % 3][j - m]) % mod
// 				}
// 				if c > 0 {
// 					l = (dp[(i + 1) % 3][j - 1] + dp[(i + 2) % 3][j - 1]) % mod
// 				}
// 				dp[i][j] = (dp[i][j] + u * l) % mod
// 		}
// 		}
// 	return (dp[0][m * n - 1] + dp[1][m * n - 1] + dp[2][m * n - 1]) % mod
// }
const mod = 1e9 + 7

// 生成一列所有合法的涂色状态
func generateValidStates(m int) [][]int {
    var states [][]int
    var dfs func(path []int)
    dfs = func(path []int) {
        if len(path) == m {
            valid := true
            for i := 1; i < m; i++ {
                if path[i] == path[i-1] {
                    valid = false
                    break
                }
            }
            if valid {
                newPath := make([]int, m)
                copy(newPath, path)
                states = append(states, newPath)
            }
            return
        }
        for c := 0; c < 3; c++ {
            dfs(append(path, c))
        }
    }
    dfs([]int{})
    return states
}

// 判断两列状态是否相邻合法
func isAdjacentValid(s1, s2 []int) bool {
    for i := 0; i < len(s1); i++ {
        if s1[i] == s2[i] {
            return false
        }
    }
    return true
}

func colorTheGrid(m int, n int) int {
    states := generateValidStates(m)
    k := len(states)
    dp := make([]int, k)
    for i := range dp {
        dp[i] = 1
    }

    for j := 1; j < n; j++ {
        newDp := make([]int, k)
        for i := 0; i < k; i++ {
            for p := 0; p < k; p++ {
                if isAdjacentValid(states[i], states[p]) {
                    newDp[i] = (newDp[i] + dp[p]) % mod
                }
            }
        }
        dp = newDp
    }

    res := 0
    for _, v := range dp {
        res = (res + v) % mod
    }
    return res
}


func main() {
	// fmt.Println(colorTheGrid(1, 1)) // 3
	// fmt.Println(colorTheGrid(1, 2)) // 6
	fmt.Println(colorTheGrid(5, 5)) // 580986	
}